505B - Mr Kitayuta's Colorful Graph - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
template <typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define of(m) find_by_order((m)); //random access of ordered set
#define all(v) (v).begin(),(v).end()
#define r_all(v) (v).rbegin(),(v).rend()
#define s(v) (v).size()
#define endl "\n";
#define NO cout << "NO\n";
#define YES cout << "YES\n";
#define No cout << "No\n";
#define Yes cout << "Yes\n";
#define PF push_front
#define PB push_back
#define MP make_pair
#define F first
#define S second

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;


void print_vec(vector<ll>& v){
    for(ll i=0; i<s(v); i++) cout << v[i] << " ";
    cout << endl
}
bool is_sorted(vector<ll>& v){
    bool x = true;
    for(ll i=0; i<s(v)-1; i++) x &= (v[i] <= v[i+1]);
    return x;
}
bool is_palindrome_s(string s) {
    string p = s;
    reverse(all(p));
    if (s == p) return true;
    else return false;
}
bool is_palindrome_n(ll n) {
    ll temp = n, sum =0 ,r;
    while(n>0)
    {
        r=n%10;
        sum = (sum*10)+r;
        n/=10;
    }
    if (temp == sum) return true;
    else return false;
}


//Graph
const int M = 100+5;
bool vis[M];
vector<ll> adj[M];
vector<pair<ll,ll>> g[M];

void dfs(ll u){
    vis[u] = 1;
    for(ll v: adj[u]){
        if(!vis[v]) dfs(v);
    }
}
ll no_of_components_of_graph(ll n){
    ll cnt = 0;
    for(ll i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i);
            cnt++;
        }
    }
    return cnt;
}
//The shortest path from a single source in a unweighted, directed graph
ll bfs_shortest_path(ll source, ll destination){
    queue<ll> q;
    q.push(source);
    vis[source] = 1;
    ll level = 0;
    for(;q.size(); ++level){
        for(ll sz = q.size();sz--;){
            ll u = q.front(); q.pop();
            if(u == destination) { return level; }
            for(ll v: adj[u]){
                if(!vis[v]){
                    q.push(v);
                    vis[v] =1;
                }
            }
        }
    }
    return -1;
}
ll bfs(ll u, ll m, ll color){
    queue<ll> q;
    q.push(u); vis[u] = 1;
    while(q.size()){
        ll sz = q.size();
        while(sz--){
            ll node = q.front(); q.pop();
            if(node == m) { return 1; }
            for(auto x: g[node]){
                if((x.S == color) && (!vis[x.F])){
                    q.push(x.F);
                    vis[x.F] = 1;
                    //cout << x.F <<endl
                }
            }
        }
    }
    return 0;
}


int main() {
    fast
    ll n, m; cin >> n >> m;
    set<ll> s;
    while(m--){
        ll u, v, color; cin >> u >> v >> color;
        s.insert(color);
        g[u].PB({v,color});
        g[v].PB({u,color});
    }
    ll q; cin >> q;
    while(q--){
        ll cnt = 0, l, r; cin >> l >> r;
        for(auto d: s){
            cnt += bfs(l, r, d);
            memset(vis, 0, sizeof vis);
        }
        cout << cnt << endl
    }
}